{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Find Minimum Time to Finish All Jobs"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #bit-manipulation #array #dynamic-programming #backtracking #bitmask"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #位运算 #数组 #动态规划 #回溯 #状态压缩"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: minimumTimeRequired"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #完成所有工作的最短时间"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个整数数组 <code>jobs</code> ，其中 <code>jobs[i]</code> 是完成第 <code>i</code> 项工作要花费的时间。</p>\n",
    "\n",
    "<p>请你将这些工作分配给 <code>k</code> 位工人。所有工作都应该分配给工人，且每项工作只能分配给一位工人。工人的 <strong>工作时间</strong> 是完成分配给他们的所有工作花费时间的总和。请你设计一套最佳的工作分配方案，使工人的 <strong>最大工作时间</strong> 得以 <strong>最小化</strong> 。</p>\n",
    "\n",
    "<p>返回分配方案中尽可能 <strong>最小</strong> 的 <strong>最大工作时间</strong> 。</p>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>jobs = [3,2,3], k = 3\n",
    "<strong>输出：</strong>3\n",
    "<strong>解释：</strong>给每位工人分配一项工作，最大工作时间是 3 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>jobs = [1,2,4,7,8], k = 2\n",
    "<strong>输出：</strong>11\n",
    "<strong>解释：</strong>按下述方式分配工作：\n",
    "1 号工人：1、2、8（工作时间 = 1 + 2 + 8 = 11）\n",
    "2 号工人：4、7（工作时间 = 4 + 7 = 11）\n",
    "最大工作时间是 11 。</pre>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 <= k <= jobs.length <= 12</code></li>\n",
    "\t<li><code>1 <= jobs[i] <= 10<sup>7</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [find-minimum-time-to-finish-all-jobs](https://leetcode.cn/problems/find-minimum-time-to-finish-all-jobs/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [find-minimum-time-to-finish-all-jobs](https://leetcode.cn/problems/find-minimum-time-to-finish-all-jobs/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[3,2,3]\\n3', '[1,2,4,7,8]\\n2']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumTimeRequired(self, jobs: List[int], k: int) -> int:\n",
    "        jobs.sort(reverse=True)\n",
    "        ans=inf\n",
    "        def dfs(sum_arr,used,job_idx):\n",
    "            nonlocal ans\n",
    "            if max(sum_arr)>=ans:\n",
    "                return\n",
    "            if job_idx==len(jobs):\n",
    "                ans=max(sum_arr)\n",
    "                return\n",
    "            if used<k:\n",
    "                sum_arr[used]=jobs[job_idx]\n",
    "                dfs(sum_arr,used+1,job_idx+1)\n",
    "                sum_arr[used]=0\n",
    "            for i in range(used):\n",
    "                sum_arr[i]+=jobs[job_idx]\n",
    "                dfs(sum_arr,used,job_idx+1)\n",
    "                sum_arr[i]-=jobs[job_idx]\n",
    "            return ans\n",
    "        dfs([0]*k,0,0)\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumTimeRequired(self, jobs: List[int], k: int) -> int:\n",
    "        path = [0]*k\n",
    "        n = len(jobs)\n",
    "        ans = inf\n",
    "\n",
    "        def dfs(i):\n",
    "            nonlocal ans\n",
    "            if max(path) >= ans:\n",
    "                return \n",
    "            if i == n:\n",
    "                ans = max(path)\n",
    "                return\n",
    "            \n",
    "            if n - i < sum(x == 0 for x in path):\n",
    "                return\n",
    "            for j in range(k):\n",
    "                if j and path[j] == path[j - 1]:\n",
    "                    continue\n",
    "                path[j] += jobs[i]\n",
    "                dfs(i + 1)\n",
    "                path[j] -= jobs[i]\n",
    "        dfs(0)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def __init__(self) -> None:\r\n",
    "        self.ans = float('inf')\r\n",
    "    \r\n",
    "    def energy(self, jobs, k):\r\n",
    "        worker = [0] * k \r\n",
    "        for j in jobs:\r\n",
    "            n = worker[0] + j\r\n",
    "            heapq.heapreplace(worker, n)\r\n",
    "        e = max(worker)\r\n",
    "        self.ans = min(self.ans, e)\r\n",
    "        return e\r\n",
    "    \r\n",
    "\r\n",
    "    def sa(self, jobs, T, fa, low, k):\r\n",
    "\r\n",
    "\r\n",
    "        while T > low:\r\n",
    "            T *= fa\r\n",
    "\r\n",
    "            n = len(jobs)\r\n",
    "\r\n",
    "            e1 = self.energy(jobs, k)\r\n",
    "\r\n",
    "            while True:\r\n",
    "                a = random.randint(0, n-1)\r\n",
    "                b = random.randint(0, n-1)\r\n",
    "                print(a, b)\r\n",
    "                if a != b:\r\n",
    "                    break\r\n",
    "            jobs[a], jobs[b] = jobs[b], jobs[a]\r\n",
    "\r\n",
    "            e2 = self.energy(jobs, k) \r\n",
    "            dt = e2 - e1\r\n",
    "            if dt >= 0 and math.exp(-dt/T) > random.random():\r\n",
    "                jobs[a], jobs[b] = jobs[b], jobs[a]\r\n",
    "                \r\n",
    "                \r\n",
    "                \r\n",
    "    \r\n",
    "    def minimumTimeRequired(self, jobs, k: int) -> int:\r\n",
    "        if k==1:\r\n",
    "            return sum(jobs)\r\n",
    "        for _ in range(100):\r\n",
    "            self.sa(jobs, 10000000, 0.9, 1e-4, k)\r\n",
    "        return self.ans \r\n",
    "    \r\n",
    "# print(Solution().minimumTimeRequired([1,2,4,7,8], 2))\r\n",
    "\r\n",
    "\r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from ctypes import *\n",
    "import mmap\n",
    "\n",
    "def translate(s):\n",
    "    res=b''\n",
    "    for l in s.split('\\n'):\n",
    "        if not ':' in l or '>:' in l: continue\n",
    "        l=l[l.find(':')+1:].strip()\n",
    "        l=l[:l.find('   ')].strip()\n",
    "        for b in l.split(' '):\n",
    "            res+=int(b,16).to_bytes(1,byteorder='little')\n",
    "    return res\n",
    "\n",
    "buf=mmap.mmap(-1,mmap.PAGESIZE,prot=mmap.PROT_READ|mmap.PROT_WRITE|mmap.PROT_EXEC)\n",
    "\n",
    "\n",
    "def compile_asm(s, ftype):\n",
    "    buf.write(translate(s))\n",
    "    return ftype(addressof(c_void_p.from_buffer(buf)))\n",
    "\n",
    "\n",
    "asm_count = compile_asm('''\n",
    "0:  55                      push   rbp\n",
    "1:  48 89 e5                mov    rbp,rsp\n",
    "4:  53                      push   rbx\n",
    "5:  48 83 ec 68             sub    rsp,0x68\n",
    "9:  48 89 7d 98             mov    QWORD PTR [rbp-0x68],rdi\n",
    "d:  89 75 94                mov    DWORD PTR [rbp-0x6c],esi\n",
    "10: 89 55 90                mov    DWORD PTR [rbp-0x70],edx\n",
    "13: 48 89 e0                mov    rax,rsp\n",
    "16: 49 89 c3                mov    r11,rax\n",
    "19: 8b 45 94                mov    eax,DWORD PTR [rbp-0x6c]\n",
    "1c: ba 01 00 00 00          mov    edx,0x1\n",
    "21: 89 c1                   mov    ecx,eax\n",
    "23: d3 e2                   shl    edx,cl\n",
    "25: 89 d0                   mov    eax,edx\n",
    "27: 48 63 d0                movsxd rdx,eax\n",
    "2a: 48 83 ea 01             sub    rdx,0x1\n",
    "2e: 48 89 55 d0             mov    QWORD PTR [rbp-0x30],rdx\n",
    "32: 48 98                   cdqe\n",
    "34: 48 8d 14 85 00 00 00    lea    rdx,[rax*4+0x0]\n",
    "3b: 00\n",
    "3c: b8 10 00 00 00          mov    eax,0x10\n",
    "41: 48 83 e8 01             sub    rax,0x1\n",
    "45: 48 01 d0                add    rax,rdx\n",
    "48: bb 10 00 00 00          mov    ebx,0x10\n",
    "4d: ba 00 00 00 00          mov    edx,0x0\n",
    "52: 48 f7 f3                div    rbx\n",
    "55: 48 6b c0 10             imul   rax,rax,0x10\n",
    "59: 48 29 c4                sub    rsp,rax\n",
    "5c: 48 89 e0                mov    rax,rsp\n",
    "5f: 48 83 c0 03             add    rax,0x3\n",
    "63: 48 c1 e8 02             shr    rax,0x2\n",
    "67: 48 c1 e0 02             shl    rax,0x2\n",
    "6b: 48 89 45 c8             mov    QWORD PTR [rbp-0x38],rax\n",
    "6f: 48 8b 45 c8             mov    rax,QWORD PTR [rbp-0x38]\n",
    "73: c7 00 00 00 00 00       mov    DWORD PTR [rax],0x0\n",
    "79: c7 45 ec 01 00 00 00    mov    DWORD PTR [rbp-0x14],0x1\n",
    "0000000000000080 <L3>:\n",
    "80: 8b 45 ec                mov    eax,DWORD PTR [rbp-0x14]\n",
    "83: f3 0f bc c0             tzcnt  eax,eax\n",
    "87: 89 45 a8                mov    DWORD PTR [rbp-0x58],eax\n",
    "8a: 8b 45 a8                mov    eax,DWORD PTR [rbp-0x58]\n",
    "8d: ba 01 00 00 00          mov    edx,0x1\n",
    "92: 89 c1                   mov    ecx,eax\n",
    "94: d3 e2                   shl    edx,cl\n",
    "96: 8b 45 ec                mov    eax,DWORD PTR [rbp-0x14]\n",
    "99: 29 d0                   sub    eax,edx\n",
    "9b: 89 45 a4                mov    DWORD PTR [rbp-0x5c],eax\n",
    "9e: 48 8b 45 c8             mov    rax,QWORD PTR [rbp-0x38]\n",
    "a2: 8b 55 a4                mov    edx,DWORD PTR [rbp-0x5c]\n",
    "a5: 48 63 d2                movsxd rdx,edx\n",
    "a8: 8b 14 90                mov    edx,DWORD PTR [rax+rdx*4]\n",
    "ab: 8b 45 a8                mov    eax,DWORD PTR [rbp-0x58]\n",
    "ae: 48 98                   cdqe\n",
    "b0: 48 8d 0c 85 00 00 00    lea    rcx,[rax*4+0x0]\n",
    "b7: 00\n",
    "b8: 48 8b 45 98             mov    rax,QWORD PTR [rbp-0x68]\n",
    "bc: 48 01 c8                add    rax,rcx\n",
    "bf: 8b 00                   mov    eax,DWORD PTR [rax]\n",
    "c1: 8d 0c 02                lea    ecx,[rdx+rax*1]\n",
    "c4: 48 8b 45 c8             mov    rax,QWORD PTR [rbp-0x38]\n",
    "c8: 8b 55 ec                mov    edx,DWORD PTR [rbp-0x14]\n",
    "cb: 48 63 d2                movsxd rdx,edx\n",
    "ce: 89 0c 90                mov    DWORD PTR [rax+rdx*4],ecx\n",
    "d1: 83 45 ec 01             add    DWORD PTR [rbp-0x14],0x1\n",
    "00000000000000d5 <L2>:\n",
    "d5: 8b 45 94                mov    eax,DWORD PTR [rbp-0x6c]\n",
    "d8: ba 01 00 00 00          mov    edx,0x1\n",
    "dd: 89 c1                   mov    ecx,eax\n",
    "df: d3 e2                   shl    edx,cl\n",
    "e1: 89 d0                   mov    eax,edx\n",
    "e3: 39 45 ec                cmp    DWORD PTR [rbp-0x14],eax\n",
    "e6: 7c 98                   jl     80 <L3>\n",
    "e8: 8b 45 94                mov    eax,DWORD PTR [rbp-0x6c]\n",
    "eb: ba 01 00 00 00          mov    edx,0x1\n",
    "f0: 89 d6                   mov    esi,edx\n",
    "f2: 89 c1                   mov    ecx,eax\n",
    "f4: d3 e6                   shl    esi,cl\n",
    "f6: 48 63 c6                movsxd rax,esi\n",
    "f9: 48 83 e8 01             sub    rax,0x1\n",
    "fd: 48 89 45 c0             mov    QWORD PTR [rbp-0x40],rax\n",
    "101:    48 63 c6                movsxd rax,esi\n",
    "104:    4c 8d 04 85 00 00 00    lea    r8,[rax*4+0x0]\n",
    "10b:    00\n",
    "10c:    8b 7d 90                mov    edi,DWORD PTR [rbp-0x70]\n",
    "10f:    48 63 c7                movsxd rax,edi\n",
    "112:    48 83 e8 01             sub    rax,0x1\n",
    "116:    48 89 45 b8             mov    QWORD PTR [rbp-0x48],rax\n",
    "11a:    48 63 c6                movsxd rax,esi\n",
    "11d:    48 89 c1                mov    rcx,rax\n",
    "120:    bb 00 00 00 00          mov    ebx,0x0\n",
    "125:    48 63 c7                movsxd rax,edi\n",
    "128:    48 89 c0                mov    rax,rax\n",
    "12b:    ba 00 00 00 00          mov    edx,0x0\n",
    "130:    49 89 da                mov    r10,rbx\n",
    "133:    4c 0f af d0             imul   r10,rax\n",
    "137:    49 89 d1                mov    r9,rdx\n",
    "13a:    4c 0f af c9             imul   r9,rcx\n",
    "13e:    4d 01 d1                add    r9,r10\n",
    "141:    48 f7 e1                mul    rcx\n",
    "144:    49 8d 0c 11             lea    rcx,[r9+rdx*1]\n",
    "148:    48 89 ca                mov    rdx,rcx\n",
    "14b:    48 63 c6                movsxd rax,esi\n",
    "14e:    48 89 c1                mov    rcx,rax\n",
    "151:    bb 00 00 00 00          mov    ebx,0x0\n",
    "156:    48 63 c7                movsxd rax,edi\n",
    "159:    48 89 c0                mov    rax,rax\n",
    "15c:    ba 00 00 00 00          mov    edx,0x0\n",
    "161:    49 89 da                mov    r10,rbx\n",
    "164:    4c 0f af d0             imul   r10,rax\n",
    "168:    49 89 d1                mov    r9,rdx\n",
    "16b:    4c 0f af c9             imul   r9,rcx\n",
    "16f:    4d 01 d1                add    r9,r10\n",
    "172:    48 f7 e1                mul    rcx\n",
    "175:    49 8d 0c 11             lea    rcx,[r9+rdx*1]\n",
    "179:    48 89 ca                mov    rdx,rcx\n",
    "17c:    48 63 d6                movsxd rdx,esi\n",
    "17f:    48 63 c7                movsxd rax,edi\n",
    "182:    48 0f af c2             imul   rax,rdx\n",
    "186:    48 8d 14 85 00 00 00    lea    rdx,[rax*4+0x0]\n",
    "18d:    00\n",
    "18e:    b8 10 00 00 00          mov    eax,0x10\n",
    "193:    48 83 e8 01             sub    rax,0x1\n",
    "197:    48 01 d0                add    rax,rdx\n",
    "19a:    bb 10 00 00 00          mov    ebx,0x10\n",
    "19f:    ba 00 00 00 00          mov    edx,0x0\n",
    "1a4:    48 f7 f3                div    rbx\n",
    "1a7:    48 6b c0 10             imul   rax,rax,0x10\n",
    "1ab:    48 29 c4                sub    rsp,rax\n",
    "1ae:    48 89 e0                mov    rax,rsp\n",
    "1b1:    48 83 c0 03             add    rax,0x3\n",
    "1b5:    48 c1 e8 02             shr    rax,0x2\n",
    "1b9:    48 c1 e0 02             shl    rax,0x2\n",
    "1bd:    48 89 45 b0             mov    QWORD PTR [rbp-0x50],rax\n",
    "1c1:    c7 45 e8 00 00 00 00    mov    DWORD PTR [rbp-0x18],0x0\n",
    "1c8:    eb 1e                   jmp    1e8 <L4>\n",
    "00000000000001ca <L5>:\n",
    "1ca:    48 8b 45 c8             mov    rax,QWORD PTR [rbp-0x38]\n",
    "1ce:    8b 55 e8                mov    edx,DWORD PTR [rbp-0x18]\n",
    "1d1:    48 63 d2                movsxd rdx,edx\n",
    "1d4:    8b 0c 90                mov    ecx,DWORD PTR [rax+rdx*4]\n",
    "1d7:    48 8b 45 b0             mov    rax,QWORD PTR [rbp-0x50]\n",
    "1db:    8b 55 e8                mov    edx,DWORD PTR [rbp-0x18]\n",
    "1de:    48 63 d2                movsxd rdx,edx\n",
    "1e1:    89 0c 90                mov    DWORD PTR [rax+rdx*4],ecx\n",
    "1e4:    83 45 e8 01             add    DWORD PTR [rbp-0x18],0x1\n",
    "00000000000001e8 <L4>:\n",
    "1e8:    8b 45 94                mov    eax,DWORD PTR [rbp-0x6c]\n",
    "1eb:    ba 01 00 00 00          mov    edx,0x1\n",
    "1f0:    89 c1                   mov    ecx,eax\n",
    "1f2:    d3 e2                   shl    edx,cl\n",
    "1f4:    89 d0                   mov    eax,edx\n",
    "1f6:    39 45 e8                cmp    DWORD PTR [rbp-0x18],eax\n",
    "1f9:    7c cf                   jl     1ca <L5>\n",
    "1fb:    c7 45 e4 01 00 00 00    mov    DWORD PTR [rbp-0x1c],0x1\n",
    "202:    e9 fa 00 00 00          jmp    301 <L6>\n",
    "0000000000000207 <L14>:\n",
    "207:    c7 45 e0 00 00 00 00    mov    DWORD PTR [rbp-0x20],0x0\n",
    "20e:    e9 d3 00 00 00          jmp    2e6 <L7>\n",
    "0000000000000213 <L13>:\n",
    "213:    c7 45 dc 3f 3f 3f 3f    mov    DWORD PTR [rbp-0x24],0x3f3f3f3f\n",
    "21a:    8b 45 e0                mov    eax,DWORD PTR [rbp-0x20]\n",
    "21d:    89 45 d8                mov    DWORD PTR [rbp-0x28],eax\n",
    "220:    e9 8f 00 00 00          jmp    2b4 <L8>\n",
    "0000000000000225 <L12>:\n",
    "225:    4c 89 c6                mov    rsi,r8\n",
    "228:    48 c1 ee 02             shr    rsi,0x2\n",
    "22c:    8b 45 e4                mov    eax,DWORD PTR [rbp-0x1c]\n",
    "22f:    8d 78 ff                lea    edi,[rax-0x1]\n",
    "232:    8b 45 e0                mov    eax,DWORD PTR [rbp-0x20]\n",
    "235:    2b 45 d8                sub    eax,DWORD PTR [rbp-0x28]\n",
    "238:    89 c2                   mov    edx,eax\n",
    "23a:    48 8b 45 b0             mov    rax,QWORD PTR [rbp-0x50]\n",
    "23e:    48 63 ca                movsxd rcx,edx\n",
    "241:    48 63 d7                movsxd rdx,edi\n",
    "244:    48 0f af d6             imul   rdx,rsi\n",
    "248:    48 01 ca                add    rdx,rcx\n",
    "24b:    8b 0c 90                mov    ecx,DWORD PTR [rax+rdx*4]\n",
    "24e:    48 8b 45 c8             mov    rax,QWORD PTR [rbp-0x38]\n",
    "252:    8b 55 d8                mov    edx,DWORD PTR [rbp-0x28]\n",
    "255:    48 63 d2                movsxd rdx,edx\n",
    "258:    8b 04 90                mov    eax,DWORD PTR [rax+rdx*4]\n",
    "25b:    39 c1                   cmp    ecx,eax\n",
    "25d:    7e 2b                   jle    28a <L9>\n",
    "25f:    4c 89 c6                mov    rsi,r8\n",
    "262:    48 c1 ee 02             shr    rsi,0x2\n",
    "266:    8b 45 e4                mov    eax,DWORD PTR [rbp-0x1c]\n",
    "269:    8d 78 ff                lea    edi,[rax-0x1]\n",
    "26c:    8b 45 e0                mov    eax,DWORD PTR [rbp-0x20]\n",
    "26f:    2b 45 d8                sub    eax,DWORD PTR [rbp-0x28]\n",
    "272:    89 c2                   mov    edx,eax\n",
    "274:    48 8b 45 b0             mov    rax,QWORD PTR [rbp-0x50]\n",
    "278:    48 63 ca                movsxd rcx,edx\n",
    "27b:    48 63 d7                movsxd rdx,edi\n",
    "27e:    48 0f af d6             imul   rdx,rsi\n",
    "282:    48 01 ca                add    rdx,rcx\n",
    "285:    8b 04 90                mov    eax,DWORD PTR [rax+rdx*4]\n",
    "288:    eb 0d                   jmp    297 <L10>\n",
    "000000000000028a <L9>:\n",
    "28a:    48 8b 45 c8             mov    rax,QWORD PTR [rbp-0x38]\n",
    "28e:    8b 55 d8                mov    edx,DWORD PTR [rbp-0x28]\n",
    "291:    48 63 d2                movsxd rdx,edx\n",
    "294:    8b 04 90                mov    eax,DWORD PTR [rax+rdx*4]\n",
    "0000000000000297 <L10>:\n",
    "297:    89 45 ac                mov    DWORD PTR [rbp-0x54],eax\n",
    "29a:    8b 45 dc                mov    eax,DWORD PTR [rbp-0x24]\n",
    "29d:    3b 45 ac                cmp    eax,DWORD PTR [rbp-0x54]\n",
    "2a0:    7e 06                   jle    2a8 <L11>\n",
    "2a2:    8b 45 ac                mov    eax,DWORD PTR [rbp-0x54]\n",
    "2a5:    89 45 dc                mov    DWORD PTR [rbp-0x24],eax\n",
    "00000000000002a8 <L11>:\n",
    "2a8:    8b 45 d8                mov    eax,DWORD PTR [rbp-0x28]\n",
    "2ab:    83 e8 01                sub    eax,0x1\n",
    "2ae:    23 45 e0                and    eax,DWORD PTR [rbp-0x20]\n",
    "2b1:    89 45 d8                mov    DWORD PTR [rbp-0x28],eax\n",
    "00000000000002b4 <L8>:\n",
    "2b4:    83 7d d8 00             cmp    DWORD PTR [rbp-0x28],0x0\n",
    "2b8:    0f 85 67 ff ff ff       jne    225 <L12>\n",
    "2be:    4c 89 c6                mov    rsi,r8\n",
    "2c1:    48 c1 ee 02             shr    rsi,0x2\n",
    "2c5:    48 8b 45 b0             mov    rax,QWORD PTR [rbp-0x50]\n",
    "2c9:    8b 55 e0                mov    edx,DWORD PTR [rbp-0x20]\n",
    "2cc:    48 63 ca                movsxd rcx,edx\n",
    "2cf:    8b 55 e4                mov    edx,DWORD PTR [rbp-0x1c]\n",
    "2d2:    48 63 d2                movsxd rdx,edx\n",
    "2d5:    48 0f af d6             imul   rdx,rsi\n",
    "2d9:    48 01 d1                add    rcx,rdx\n",
    "2dc:    8b 55 dc                mov    edx,DWORD PTR [rbp-0x24]\n",
    "2df:    89 14 88                mov    DWORD PTR [rax+rcx*4],edx\n",
    "2e2:    83 45 e0 01             add    DWORD PTR [rbp-0x20],0x1\n",
    "00000000000002e6 <L7>:\n",
    "2e6:    8b 45 94                mov    eax,DWORD PTR [rbp-0x6c]\n",
    "2e9:    ba 01 00 00 00          mov    edx,0x1\n",
    "2ee:    89 c1                   mov    ecx,eax\n",
    "2f0:    d3 e2                   shl    edx,cl\n",
    "2f2:    89 d0                   mov    eax,edx\n",
    "2f4:    39 45 e0                cmp    DWORD PTR [rbp-0x20],eax\n",
    "2f7:    0f 8c 16 ff ff ff       jl     213 <L13>\n",
    "2fd:    83 45 e4 01             add    DWORD PTR [rbp-0x1c],0x1\n",
    "0000000000000301 <L6>:\n",
    "301:    8b 45 e4                mov    eax,DWORD PTR [rbp-0x1c]\n",
    "304:    3b 45 90                cmp    eax,DWORD PTR [rbp-0x70]\n",
    "307:    0f 8c fa fe ff ff       jl     207 <L14>\n",
    "30d:    4c 89 c6                mov    rsi,r8\n",
    "310:    48 c1 ee 02             shr    rsi,0x2\n",
    "314:    8b 45 90                mov    eax,DWORD PTR [rbp-0x70]\n",
    "317:    8d 50 ff                lea    edx,[rax-0x1]\n",
    "31a:    8b 45 94                mov    eax,DWORD PTR [rbp-0x6c]\n",
    "31d:    bf 01 00 00 00          mov    edi,0x1\n",
    "322:    89 c1                   mov    ecx,eax\n",
    "324:    d3 e7                   shl    edi,cl\n",
    "326:    89 f8                   mov    eax,edi\n",
    "328:    8d 48 ff                lea    ecx,[rax-0x1]\n",
    "32b:    48 8b 45 b0             mov    rax,QWORD PTR [rbp-0x50]\n",
    "32f:    48 63 c9                movsxd rcx,ecx\n",
    "332:    48 63 d2                movsxd rdx,edx\n",
    "335:    48 0f af d6             imul   rdx,rsi\n",
    "339:    48 01 ca                add    rdx,rcx\n",
    "33c:    8b 04 90                mov    eax,DWORD PTR [rax+rdx*4]\n",
    "33f:    4c 89 dc                mov    rsp,r11\n",
    "342:    48 8b 5d f8             mov    rbx,QWORD PTR [rbp-0x8]\n",
    "346:    c9                      leave\n",
    "347:    c3                      ret\n",
    "''', CFUNCTYPE(c_int,POINTER(c_int),c_int))\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def minimumTimeRequired(self, jobs: List[int], k: int) -> int:\n",
    "        n = len(jobs)\n",
    "        a=(c_int*n)(*jobs)\n",
    "        return asm_count(a, n, k)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumTimeRequired(self, jobs: List[int], k: int) -> int:\n",
    "        n = len(jobs)\n",
    "        dp = [[inf] * (1 << n) for i in range(k + 1)]\n",
    "\n",
    "        dp[1][0] = 0\n",
    "        for s in range(1 << n):\n",
    "            for i in range(n):\n",
    "                if s & (1 << i) > 0:\n",
    "                    sub_s = s ^ (1 << i)\n",
    "                    dp[1][s] = dp[1][sub_s] + jobs[i]\n",
    "                    break\n",
    "\n",
    "        for kk in range(2, k + 1):\n",
    "            #dp[kk][0] = 0\n",
    "            for s in range(1, 1 << n):\n",
    "\n",
    "                sums = inf\n",
    "                ones = s.bit_count()\n",
    "                if ones < kk:\n",
    "                    dp[kk][s] = dp[kk-1][s]\n",
    "                    continue\n",
    "                for i in range(n):\n",
    "                    if s & (1 << i) > 0:\n",
    "                        sums = jobs[i]\n",
    "                        dp[kk][s] = max(dp[kk-1][s ^ (1 << i)], jobs[i])\n",
    "                        res_s = s ^ 1 << i\n",
    "                        break\n",
    "                \n",
    "                x = res_s\n",
    "                while x > 0:\n",
    "                    y = x ^ res_s\n",
    "                    p1 = dp[kk-1][y]\n",
    "                    p2 = dp[1][x] + sums\n",
    "                    if p1 > p2:\n",
    "                        if p1 < dp[kk][s]:\n",
    "                            dp[kk][s] = p1\n",
    "                    else:\n",
    "                        if p2 < dp[kk][s]:\n",
    "                            dp[kk][s] = p2        \n",
    "\n",
    "                    x = res_s & (x - 1)\n",
    "\n",
    "        return dp[-1][-1]\n",
    "\n",
    "\n",
    "            \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumTimeRequired(self, jobs: List[int], k: int) -> int:\n",
    "        njob = len(jobs)\n",
    "        def lt(x, y):\n",
    "            if x[0] < y[0]:\n",
    "                return 1\n",
    "            elif x[0] > y[0]:\n",
    "                return 0\n",
    "            else:\n",
    "                if x[1] < y[1]: \n",
    "                    return 1\n",
    "            return 0\n",
    "\n",
    "        \n",
    "        def work(status):\n",
    "            # print(status)\n",
    "            if status in dic:\n",
    "                return dic[status][:]\n",
    "            j = 0\n",
    "            res = [1e10, 1e10]\n",
    "            while j < njob:\n",
    "                if (status >> j) & 1 == 1:\n",
    "                    r =  work(status & ~(1 << j))\n",
    "                    r[1] += jobs[j]\n",
    "                    if r[1] > mx:\n",
    "                        r[1] = jobs[j]\n",
    "                        r[0] += 1\n",
    "                    if lt(r, res) == 1:\n",
    "                        res = r[:]\n",
    "                j += 1\n",
    "            dic[status] = res[:]\n",
    "            return res[:]\n",
    "\n",
    "        full = pow(2, njob) - 1\n",
    "        # mx = 11\n",
    "        # a = work(full)\n",
    "        # print(a)\n",
    "        lower = max(jobs)\n",
    "        upper = sum(jobs) \n",
    "        while lower <= upper:\n",
    "            mx = (lower + upper) // 2\n",
    "            dic = {0: [0, 0]}\n",
    "            a = work(full)\n",
    "            # print(mx, a)\n",
    "            if a[0] < k:\n",
    "                upper = mx - 1\n",
    "            else:\n",
    "                lower = mx + 1\n",
    "        return upper + 1\n",
    "\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumTimeRequired(self, jobs: List[int], k: int) -> int:\n",
    "        \n",
    "        n = len(jobs)\n",
    "        \n",
    "        get = [0] * (1 << n)\n",
    "        for i in range(1 << n):\n",
    "            get[i] = sum(jobs[j] for j in range(n) if i & (1 << j))\n",
    "        \n",
    "        @cache\n",
    "        def dp(i, remain):\n",
    "            if i == k and remain == 0:\n",
    "                return 0\n",
    "            if i == k - 1:\n",
    "                return get[remain]\n",
    "            tmp = 1<<(len(bin(remain))-3)\n",
    "            r = remain - tmp\n",
    "            \n",
    "            res = 10 ** 9\n",
    "            while True:\n",
    "                if get[r] < res:\n",
    "                    res = min(res, max(dp(i + 1, (r+tmp)^ remain), get[r+tmp]))\n",
    "                if r==0:\n",
    "                    break\n",
    "                r = (r - 1) & remain\n",
    "            return res\n",
    "            \n",
    "        if k == len(jobs):\n",
    "            return max(jobs)\n",
    "        res = dp(0, 2 ** n - 1)\n",
    "        return res\n",
    "        \n",
    "# class Solution:\n",
    "#     def minimumTimeRequired(self, jobs: List[int], k: int) -> int:\n",
    "        \n",
    "#         n = len(jobs)\n",
    "        \n",
    "#         get = [0] * (1 << n)\n",
    "#         for i in range(1 << n):\n",
    "#             get[i] = sum(jobs[j] for j in range(n) if i & (1 << j))\n",
    "        \n",
    "#         @cache\n",
    "#         def dp(i, remain):\n",
    "#             if i == k and remain == 0:\n",
    "#                 return 0\n",
    "#             if i == k - 1:\n",
    "#                 return get[remain]\n",
    "#             r = remain\n",
    "#             res = 10 ** 9\n",
    "#             while r:\n",
    "#                 if get[r] < res:\n",
    "#                     res = min(res, max(dp(i + 1, r ^ remain), get[r]))\n",
    "#                 r = (r - 1) & remain\n",
    "#             return res\n",
    "            \n",
    "#         if k == len(jobs):\n",
    "#             return max(jobs)\n",
    "#         res = dp(0, 2 ** n - 1)\n",
    "#         #dp.cache_clear()\n",
    "#         return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumTimeRequired(self, jobs: List[int], k: int) -> int:\n",
    "        jobs.sort()\n",
    "        n = len(jobs)\n",
    "        mn = (n + k - 1) // k\n",
    "\n",
    "        D = {1 << (n - 1 - i) : jobs[i] for i in range(n)}\n",
    "        def get_sum(stat):\n",
    "            if stat in D: return D[stat]\n",
    "            lo = -stat & stat\n",
    "            D[stat] = get_sum(stat - lo) + D[lo]\n",
    "            return D[stat]\n",
    "        for i in range(1, (1 << n)): get_sum(i)\n",
    "        D[0] = 0\n",
    "        sorted_sum = sorted(zip(D.values(), D.keys()))\n",
    "        print(jobs)\n",
    "        def check(M):\n",
    "            def dfs(i, stat):\n",
    "                if i == k: return stat == 0\n",
    "                lo = -stat & stat\n",
    "                stat -= lo\n",
    "                tar = M - D[lo]\n",
    "                r = bisect.bisect_left(sorted_sum, (tar, (1 << n) - 1))\n",
    "                for l in range(r - 1, -1, -1):\n",
    "                    if stat | sorted_sum[l][1] == stat and dfs(i + 1, stat ^ sorted_sum[l][1]): return True\n",
    "                return False\n",
    "            return dfs(0, (1 << n) - 1)\n",
    "\n",
    "        #[L, R]\n",
    "        L, R = jobs[0], sum(jobs[-mn : ])\n",
    "        while L < R:\n",
    "            M = (L + R) // 2\n",
    "            if check(M): R = M\n",
    "            else: L = M + 1\n",
    "        return L"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumTimeRequired(self, jobs: List[int], k: int) -> int:\n",
    "        \n",
    "        jobs = sorted(jobs, reverse=True)\n",
    "        \n",
    "        @functools.lru_cache(100000)\n",
    "        def f(st, mx):\n",
    "            # print(st)\n",
    "            if st == 0: return 0\n",
    "            \n",
    "            exs = [i for i in range(len(jobs)) if (1<<i) & st]\n",
    "            # print(exs)\n",
    "            # print(mx)\n",
    "            \n",
    "            mi = int(1e11)\n",
    "            for cs in range(1 << (len(exs)-1)):\n",
    "                # print('cs', bin(cs))\n",
    "                su = sum([jobs[exs[i+1]] for i in range(len(exs)-1) if (1<<i) & cs])\n",
    "                # print(jobs[exs[0]], su)\n",
    "                if mx >= su + jobs[exs[0]] and mx - su - jobs[exs[0]] < min([int(1e11)] + [jobs[exs[i+1]] for i in range(len(exs)-1) if not (1<<i) & cs]):\n",
    "                    # print('ok')\n",
    "                    pst = st ^ (1 << exs[0])\n",
    "                    for i in range(len(exs)-1):\n",
    "                        if (1<<i) & cs:\n",
    "                            pst ^= (1 << exs[i+1])\n",
    "                    mi = min(mi, 1 + f(pst, mx))\n",
    "                    \n",
    "            return mi\n",
    "        \n",
    "        print(f((1<<len(jobs))-1, 11))\n",
    "        \n",
    "        l,r = 1, int(1e11)\n",
    "        \n",
    "        while l < r:\n",
    "            mid = (l + r) //2\n",
    "            if f((1<<len(jobs))-1, mid) > k:\n",
    "                l = mid + 1\n",
    "            else:\n",
    "                r = mid\n",
    "                \n",
    "        return l"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumTimeRequired(self, jobs: List[int], k: int) -> int:\n",
    "        @cache\n",
    "        def dfs(i,st):\n",
    "            if i==k:\n",
    "                return 0 if st==(1<<n)-1 else inf\n",
    "            cands = [j for j in range(n) if not st&1<<j]\n",
    "            j = cands.pop()\n",
    "            res = max(jobs[j],dfs(i+1,st|1<<j))\n",
    "            for x in range(1,len(cands)-(k-i-1)+1):\n",
    "                for sub in combinations(cands,x):\n",
    "                    w = sum(jobs[y] for y in sub)+jobs[j]\n",
    "                    st2 = sum(1<<y for y in sub)|1<<j\n",
    "                    res = min(res, max(w,dfs(i+1,st|st2)))\n",
    "            return res\n",
    "\n",
    "        n = len(jobs)\n",
    "        return dfs(0,0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumTimeRequired(self, jobs: List[int], k: int) -> int:\n",
    "        if k == 12:\n",
    "            return max(jobs)\n",
    "        if k == 11:\n",
    "            if len(jobs) == 11:\n",
    "                return max(jobs)\n",
    "            jobs.sort()\n",
    "            return max(jobs[0] + jobs[1], jobs[-1])\n",
    "        # k <= 10\n",
    "        self.k = k\n",
    "        self.ans = sum(jobs)\n",
    "        \n",
    "        memo = [set() for _ in range(len(jobs))]\n",
    "        \n",
    "        def search(i, t):\n",
    "            if i == len(jobs):\n",
    "                self.ans = min(self.ans, max(t))\n",
    "                return\n",
    "            t_tuple = tuple(sorted(t))\n",
    "            if t_tuple[-1] >= self.ans:\n",
    "                return\n",
    "            # t_tuple = tuple(t)\n",
    "            if t_tuple in memo[i]:\n",
    "                return\n",
    "            memo[i].add(t_tuple)\n",
    "            \n",
    "            for p in range(self.k):\n",
    "                t[p] += jobs[i]\n",
    "                search(i + 1, t)\n",
    "                t[p] -= jobs[i]\n",
    "            \n",
    "        search(0, [0] * k)\n",
    "        return self.ans\n",
    "                \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Also timeout\n",
    "class Solution(object):\n",
    "    def minimumTimeRequired(self, jobs, k):\n",
    "        lo = max(jobs)\n",
    "        hi = sum(jobs)\n",
    "        n = len(jobs)\n",
    "        costState = [0]*4096\n",
    "        for i in range(4096):\n",
    "            ret =0\n",
    "            for j in range(n):\n",
    "                if i & (1<<j) !=0:\n",
    "                    ret += jobs[j]\n",
    "            costState[i] = ret\n",
    "        mem ={}\n",
    "        def dfs(state,th,idx):\n",
    "            #print(state,th,idx)\n",
    "            if state == 0 :\n",
    "                return True\n",
    "            if idx ==k:\n",
    "                return False\n",
    "            if (idx,state) in mem:\n",
    "                return False\n",
    "            subSet =state\n",
    "            while subSet>0:\n",
    "                #print(subSet,\"subset ,\", idx,state)\n",
    "                if costState[subSet] > th:\n",
    "                    pass\n",
    "                else:\n",
    "                    if dfs(state -subSet,th,idx +1):\n",
    "                        return True\n",
    "                subSet = (subSet-1) & state\n",
    "            mem[(idx,state)] =1\n",
    "            return False\n",
    "\n",
    "\n",
    "        while lo < hi:\n",
    "            mem={}\n",
    "            mid = (lo + hi) >>1\n",
    "            #print(mid)\n",
    "            if dfs((1<<n)-1,mid,0):\n",
    "                hi = mid\n",
    "            else:\n",
    "                lo = mid+1\n",
    "        return lo"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumTimeRequired(self, jobs: List[int], k: int) -> int:\n",
    "        \n",
    "        def backtrack(used, current, cnt, limit, memo):\n",
    "            \n",
    "            key = (used, current, cnt)\n",
    "            if key in memo:\n",
    "                return memo[key]\n",
    "            \n",
    "            if cnt > k:\n",
    "                memo[key] = False\n",
    "                return memo[key]\n",
    "            \n",
    "            allocated_all = True\n",
    "            current_full = True\n",
    "            for i in range(len(jobs)):\n",
    "                if used & (1 << i):\n",
    "                    continue\n",
    "                allocated_all = False\n",
    "                if jobs[i] + current <= limit:\n",
    "                    current_full = False\n",
    "                    if backtrack(used + (1 << i), current + jobs[i], cnt + (current == 0), limit, memo):\n",
    "                        memo[key] = True\n",
    "                        return memo[key]\n",
    "            \n",
    "            if allocated_all:\n",
    "                if cnt <= k:\n",
    "                    memo[key] = True\n",
    "                    return memo[key]\n",
    "                else:\n",
    "                    memo[key] = False\n",
    "                    return memo[key]\n",
    "            \n",
    "            if current_full:\n",
    "                memo[key] = backtrack(used, 0, cnt, limit, memo)\n",
    "                return memo[key]\n",
    "            \n",
    "            memo[key] = False\n",
    "            return memo[key]\n",
    "        \n",
    "        l = max(jobs)\n",
    "        r = sum(jobs)\n",
    "        while l < r:\n",
    "            mid = (l + r) // 2\n",
    "            if backtrack(0, 0, 0, mid, {}):\n",
    "                r = mid\n",
    "            else:\n",
    "                l = mid + 1\n",
    "        return l"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumTimeRequired(self, jobs: List[int], k: int) -> int:\n",
    "        @cache\n",
    "        def dfs(i,st):\n",
    "            if st==(1<<n)-1:\n",
    "                return 0\n",
    "            if i==k:\n",
    "                return inf\n",
    "            cands = [j for j in range(n) if not st&1<<j]\n",
    "            j = cands.pop()\n",
    "            res = max(jobs[j],dfs(i+1,st|1<<j))\n",
    "            for x in range(1,len(cands)+1):\n",
    "                for sub in combinations(cands,x):\n",
    "                    w = sum(jobs[y] for y in sub)+jobs[j]\n",
    "                    st2 = sum(1<<y for y in sub)|1<<j\n",
    "                    res = min(res, max(w,dfs(i+1,st|st2)))\n",
    "            return res\n",
    "\n",
    "        n = len(jobs)\n",
    "        return dfs(0,0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumTimeRequired(self, jobs: List[int], total_workers: int) -> int:\n",
    "        LARGE = 10**10\n",
    "        \n",
    "        cache = [{} for _ in range(13)]\n",
    " \n",
    "        def helper(remaining, k):\n",
    "            if remaining in cache[k]:\n",
    "                return cache[k][remaining]\n",
    "\n",
    "            if k == 2:\n",
    "                cursum = sum(remaining)\n",
    "                minres = LARGE\n",
    "                for i in range(len(remaining)):\n",
    "                    for comb in itertools.combinations(remaining, i):\n",
    "                        sum_unassigned = sum(comb)\n",
    "                        taken_sum = cursum - sum_unassigned\n",
    "                        minres = min(minres, max(sum_unassigned, taken_sum))\n",
    "                cache[k][remaining] = minres\n",
    "                return minres\n",
    "\n",
    "            if k >= len(remaining):\n",
    "                return max(jobs)\n",
    "            \n",
    "            minres = LARGE\n",
    "            cursum = sum(remaining)\n",
    "            budget = cursum//k\n",
    "            \n",
    "            for comb in itertools.product([0,1], repeat=len(remaining)):\n",
    "                unassigned = tuple(a for a,b in zip(remaining, comb) if b)\n",
    "                sum_unassigned = sum(unassigned)\n",
    "                taken_sum = cursum - sum_unassigned\n",
    "                \n",
    "                if taken_sum >= budget:\n",
    "                    res = max(helper(unassigned, k-1), taken_sum)\n",
    "                    minres = min(minres, res)\n",
    "            cache[k][remaining] = minres\n",
    "            return minres\n",
    "            \n",
    "        return helper(tuple(sorted(jobs)), total_workers)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import gc;gc.disable()\n",
    "class Solution:\n",
    "    def minimumTimeRequired(self, A, k) -> int:\n",
    "        n = len(A)\n",
    "        random.shuffle(A)\n",
    "        pq = [0]*k\n",
    "        for v in A:\n",
    "            heappush(pq,heappop(pq)+v)\n",
    "        ans = max(pq)\n",
    "        @cache\n",
    "        def dfs(Ai, grps):\n",
    "            if Ai == n:\n",
    "                nonlocal ans\n",
    "                ans = grps[-1]\n",
    "                return\n",
    "\n",
    "            for i,v in enumerate(grps):\n",
    "                if i>0 and grps[i-1]==v: continue\n",
    "                nv = v + A[Ai]\n",
    "                if nv >= ans: break\n",
    "                dfs(Ai+1, tuple(sorted(grps[:i] + (nv,) + grps[i+1:])))\n",
    "\n",
    "        dfs(0, (0,)*k)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumTimeRequired(self, jobs: List[int], k: int) -> int:\n",
    "        l = len(jobs)\n",
    "        p2 = [2**i for i in range(13)]\n",
    "        @cache\n",
    "        def dfs(l, k):\n",
    "            if k == 1: return sum(l)\n",
    "            s = sum(l)\n",
    "            m = 1000000000\n",
    "            ss = 0\n",
    "            for i in range(len(l)):\n",
    "                ss += l[i]\n",
    "                if ss >= s // k:\n",
    "                    m = max(ss, dfs(tuple(l[i+1:]), k-1))\n",
    "                    break\n",
    "            for i in range(p2[len(l)]-1):\n",
    "                b = bin(i)[2:]\n",
    "                nl = []\n",
    "                for j in range(len(b)):\n",
    "                    if b[j] == '1':\n",
    "                        nl.append(l[j])\n",
    "                ss = s - sum(nl)\n",
    "                if ss < m:\n",
    "                    m = min(m, max(ss, dfs(tuple(nl), k-1)))\n",
    "            return m\n",
    "        return dfs(tuple(sorted(jobs)), k)\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "def inc(m):\n",
    "    for i in range(len(m) - 1, -1, -1):\n",
    "        if m[i] == 0:\n",
    "            m[i] = 1\n",
    "            return True\n",
    "        else:\n",
    "            m[i] = 0\n",
    "    return False\n",
    "class Solution:\n",
    "    def minimumTimeRequired(self, jobs: List[int], k: int) -> int:\n",
    "        n = len(jobs)\n",
    "        inf = sum(jobs)\n",
    "        jobs.sort()\n",
    "        @lru_cache(None)\n",
    "        def f(i, a):\n",
    "            #print(i, a)\n",
    "            if len(a) <= i:\n",
    "                return max(a)\n",
    "            if i == 1:\n",
    "                return sum(a)\n",
    "            ret = inf\n",
    "            m = [0] * len(a)\n",
    "            maxa = max(a)\n",
    "            while inc(m):\n",
    "                if len(a) - sum(m) < i - 1:\n",
    "                    continue\n",
    "                x = []\n",
    "                y = []\n",
    "                for j in range(len(a)):\n",
    "                    if m[j]:\n",
    "                        x.append(a[j])\n",
    "                    else:\n",
    "                        y.append(a[j])\n",
    "                if ret == maxa:\n",
    "                    return ret\n",
    "                if sum(x) < ret:\n",
    "                    ret = min(ret, max(sum(x), f(i - 1, tuple(y))))\n",
    "            return ret\n",
    "        return f(k, tuple(jobs))\n",
    "\n",
    "            \n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumTimeRequired(self, jobs: List[int], k: int) -> int:\n",
    "        @lru_cache(None)\n",
    "        def search(subjobs:tuple, workers:int)->int:\n",
    "            if len(subjobs) == workers:\n",
    "                return max(subjobs)\n",
    "            if  workers == 1:\n",
    "                return sum(subjobs)\n",
    "            \n",
    "            wrong_way = []\n",
    "            result = sum(subjobs)\n",
    "            indexes = list(range(len(subjobs)))\n",
    "            for n in range(1,len(subjobs)):\n",
    "                cut = True\n",
    "                for sub in combinations(indexes,n):\n",
    "                    this = [subjobs[i] for i in sub]\n",
    "                    a = sum(this)\n",
    "                    if a > result:\n",
    "                        wrong_way.append(set(sub))\n",
    "                        continue\n",
    "\n",
    "                    ssub = set(sub)\n",
    "                    if any(footprint < ssub for footprint in wrong_way):\n",
    "                        continue\n",
    "                    other = tuple(subjobs[i] for i in indexes if not i in sub)\n",
    "\n",
    "                    b = search(other,workers-1)\n",
    "                    result = min(result,max(a,b))\n",
    "                    if a > b:\n",
    "                        wrong_way.append(set(sub))\n",
    "                    cut = False\n",
    "                if cut:\n",
    "                    break\n",
    "            return result\n",
    "\n",
    "        return search(tuple(jobs),k)\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumTimeRequired(self, jobs: List[int], k: int) -> int:\n",
    "        l = len(jobs)\n",
    "        M = 1000000000\n",
    "        p2 = [2**i for i in range(13)]\n",
    "        @cache\n",
    "        def dfs(l, k):\n",
    "            if k == 1: return sum(l)\n",
    "            s = sum(l)\n",
    "            m = M\n",
    "            for i in range(1, p2[len(l)]-1):\n",
    "                b = bin(i)[2:]\n",
    "                nl = []\n",
    "                for j in range(len(b)):\n",
    "                    if b[j] == '1':\n",
    "                        nl.append(l[j])\n",
    "                ss = s - sum(nl)\n",
    "                if ss < m and len(nl) >= k-1:\n",
    "                    m = min(m, max(ss, dfs(tuple(nl), k-1)))\n",
    "            return m\n",
    "        return dfs(tuple(sorted(jobs)), k)\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumTimeRequired(self, jobs: List[int], k: int) -> int:\n",
    "        @cache\n",
    "        def dfs(i,st):\n",
    "            if st==0:\n",
    "                return 0\n",
    "            if i==k or k-i>bin(st).count('1'):\n",
    "                return inf\n",
    "            res = inf\n",
    "            sub, x = st, st.bit_length()-1\n",
    "            while sub:\n",
    "                if sub&1<<x:\n",
    "                    res = min(res, max(A[sub],dfs(i+1,st^sub)))\n",
    "                sub = (sub-1)&st\n",
    "            return res\n",
    "\n",
    "        n = len(jobs)\n",
    "        A = [0]*(1<<n)\n",
    "        for st in range(1,1<<n):\n",
    "            x = st.bit_length()-1\n",
    "            A[st] = jobs[x]+A[st^1<<x]\n",
    "        return dfs(0,(1<<n)-1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumTimeRequired(self, jobs: List[int], K: int) -> int:\n",
    "        jobs.sort()\n",
    "        n = len(jobs)\n",
    "        init = 2 ** n - 1\n",
    "        d = {0:(0, 0, 0), init:(n,sum(jobs),jobs[-1])}\n",
    "        D = {2**i:jobs[i] for i in range(n)}\n",
    "\n",
    "        @lru_cache(None)\n",
    "        def dp(k, state):\n",
    "            num, total, largest = d[state]\n",
    "            if k == num: return largest\n",
    "            if k == 1: return total\n",
    "            i, stack, ans = 1, [0], total\n",
    "            while i <= state:\n",
    "                if i & state:\n",
    "                    stop = len(stack)\n",
    "                    for idx in range(stop):\n",
    "                        j = stack[idx]\n",
    "                        a, b, _ = d[j]\n",
    "                        x, y = i + j, b + D[i]\n",
    "                        cur = total - y\n",
    "                        if x not in d:\n",
    "                            d[x] = a+1, y, D[i]\n",
    "                        stack.append(x)\n",
    "                        if k - 1 <= a + 1 < num and largest <= cur < ans:\n",
    "                            ans = min(ans, max(cur, dp(k-1, x)))\n",
    "                i <<= 1\n",
    "            return ans\n",
    "\n",
    "        return dp(K, init)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumTimeRequired(self, jobs: List[int], k: int) -> int:\n",
    "        current_status = set()\n",
    "        current_status.add(tuple(0 for i in range(k)))\n",
    "        jobs.sort(reverse=True)\n",
    "        for i in range(len(jobs)):\n",
    "            next_status = set()\n",
    "            for status in current_status:\n",
    "                for j in range(k):\n",
    "                    new = list(status)\n",
    "                    new[j] += jobs[i]\n",
    "                    for m in range(j, 0, -1):\n",
    "                        if new[m] > new[m - 1]:\n",
    "                            new[m], new[m - 1] = new[m - 1], new[m]\n",
    "                        else:\n",
    "                            break\n",
    "                    # print(new)\n",
    "                    next_status.add(tuple(new))\n",
    "            remaining_jobs = sum(jobs[i+1:])\n",
    "            threshold = min(max(status[0], status[-1] + remaining_jobs) for status in next_status)\n",
    "            current_status = [status for status in next_status if status[0] <= threshold]\n",
    "            # print(i, current_status)\n",
    "        return min(status[0] for status in current_status)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumTimeRequired(self, jobs: List[int], k: int) -> int:\n",
    "        @lru_cache(None)\n",
    "        def help(state, k):\n",
    "            if k == 1:\n",
    "                x = state.bit_length()-1\n",
    "                return 0 if state==0 else help(state-(1<<x), 1) + jobs[x]\n",
    "            res = float('inf')\n",
    "            x = y = state & (state-1)\n",
    "            while y:\n",
    "                y = x & (y-1)\n",
    "                res = min(res, max(help(x-y,k-1), help(y+state-x, 1)))\n",
    "            return res\n",
    "\n",
    "        n = len(jobs)\n",
    "        return help((1 << n)-1, k)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumTimeRequired(self, jobs: List[int], k: int) -> int:\n",
    "        N = len(jobs)\n",
    "        S = [sum(jobs[k] for k in range(N) if cur & 1 << k) for cur in range(1 << N)]\n",
    "        @lru_cache(maxsize=None)\n",
    "        def dfs(state, workers):\n",
    "            if workers == 1:\n",
    "                return S[state]\n",
    "            cur = state\n",
    "            res = 0x7FFFFFFF\n",
    "            while True:\n",
    "                if S[cur] < res:\n",
    "                    res = min(res, max(S[cur], dfs(state ^ cur, workers - 1)))\n",
    "                if not (cur := (cur - 1) & state):\n",
    "                    return res\n",
    "        return dfs((1 << N) - 1, k)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumTimeRequired(self, jobs: List[int], k: int) -> int:\n",
    "        @lru_cache(None)\n",
    "        def search(subjobs:tuple, workers:int)->int:\n",
    "            if len(subjobs) == workers:\n",
    "                return max(subjobs)\n",
    "            if  workers == 1:\n",
    "                return sum(subjobs)\n",
    "            \n",
    "            wrong_way = []\n",
    "            result = sum(subjobs)\n",
    "            indexes = list(range(len(subjobs)))\n",
    "            for n in range(1,len(subjobs)):\n",
    "                cut = True\n",
    "                for sub in combinations(indexes,n):\n",
    "                    this = [subjobs[i] for i in sub]\n",
    "                    a = sum(this)\n",
    "                    if a > result:\n",
    "                        continue\n",
    "\n",
    "                    other = tuple(subjobs[i] for i in indexes if not i in sub)\n",
    "\n",
    "                    b = search(other,workers-1)\n",
    "                    result = min(result,max(a,b))\n",
    "                    cut = False\n",
    "                if cut:\n",
    "                    break\n",
    "            return result\n",
    "\n",
    "        return search(tuple(jobs),k)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumTimeRequired(self, jobs: List[int], k: int) -> int:\n",
    "        return get_min_time(jobs, k)\n",
    "\n",
    "def get_min_time(jobs, k):\n",
    "    if k == 1:\n",
    "        return sum(jobs)\n",
    "    packs = [0] * k\n",
    "    jobs.sort()\n",
    "    job_count = len(jobs)\n",
    "    for idx, job_time in enumerate(jobs):\n",
    "        k_idx = idx % k\n",
    "        packs[k_idx] += job_time\n",
    "    cur_time = max(*packs)\n",
    "    packs = [0] * k\n",
    "    dedup_buff = set()\n",
    "\n",
    "    return get_recur_min(jobs, job_count, 0, packs, cur_time, dedup_buff)\n",
    "\n",
    "\n",
    "def get_recur_min(jobs, job_count, job_index, packs, cur_min, dedup_buff):\n",
    "    if job_index == job_count:\n",
    "        cur_min = min(cur_min, max(*packs))\n",
    "        return cur_min\n",
    "\n",
    "    new_packs = list(packs)\n",
    "    new_packs.sort()\n",
    "    new_packs.append(job_index)\n",
    "    dedup_key = tuple(new_packs)\n",
    "\n",
    "    if dedup_key in dedup_buff:\n",
    "       return cur_min\n",
    "\n",
    "    for idx, cur_pack in enumerate(packs):\n",
    "        if cur_pack + jobs[job_index] >= cur_min:\n",
    "            continue\n",
    "\n",
    "        packs[idx] += jobs[job_index]\n",
    "        cur_min = min(cur_min, get_recur_min(jobs, job_count, job_index + 1, packs, cur_min, dedup_buff))\n",
    "        packs[idx] -= jobs[job_index]\n",
    "        dedup_buff.add(dedup_key)\n",
    "\n",
    "    return cur_min\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumTimeRequired(self, jobs: List[int], k: int) -> int:\n",
    "        # 记忆化搜索+预处理+位运算+子集枚举+剪枝\n",
    "        n = len(jobs)\n",
    "        uplimit = 1 << n\n",
    "        sms = [0] * uplimit\n",
    "        one = [0] * uplimit\n",
    "        # 预处理每个mask的时间和以及1的个数\n",
    "        for bit in range(1, uplimit):\n",
    "            # prebit是去掉最低位1后的数字\n",
    "            prebit = bit & (bit - 1)\n",
    "            # lowbit是只包含最低位1的数字\n",
    "            lowbit = bit & -bit\n",
    "            one[bit] = one[prebit] + 1\n",
    "            sms[bit] = sms[prebit] + jobs[len(bin(lowbit)) - 3]\n",
    "\n",
    "        @functools.lru_cache(None)\n",
    "        def cal(p, mask):\n",
    "            if mask == 0:\n",
    "                # 已经没有工作了, 不再需要时间\n",
    "                return 0\n",
    "            if p == k:\n",
    "                # 此时mask不是0, 还有额外工作, 属于无效情况\n",
    "                return float('inf')\n",
    "            mn = float('inf')\n",
    "            cur = mask\n",
    "            while cur:\n",
    "                # 子集枚举\n",
    "                sm = sms[cur]\n",
    "                if sm < mn:\n",
    "                    # 只有当sm小于当前mn才有意义继续计算\n",
    "                    nex = mask ^ cur\n",
    "                    if k - p - 1 <= one[nex]:\n",
    "                        # 剪枝, 只有当后面的工作数>=人数时才继续计算\n",
    "                        mn = min(mn, max(sm, cal(p + 1, nex)))\n",
    "                cur = (cur - 1) & mask\n",
    "            return mn\n",
    "\n",
    "        return cal(0, uplimit - 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def minimumTimeRequired(self, jobs: List[int], k: int) -> int:\r\n",
    "        # 记忆化搜索+预处理+位运算+子集枚举+剪枝\r\n",
    "        n = len(jobs)\r\n",
    "        uplimit = 1 << n\r\n",
    "        sms = [0] * uplimit\r\n",
    "        one = [0] * uplimit\r\n",
    "        # 预处理每个mask的时间和以及1的个数\r\n",
    "        for bit in range(uplimit):\r\n",
    "            sm, cnt = 0, 0\r\n",
    "            cur = bit\r\n",
    "            while cur:\r\n",
    "                lowbit = cur & -cur\r\n",
    "                sm += jobs[len(bin(lowbit)) - 3]\r\n",
    "                cnt += 1\r\n",
    "                cur -= lowbit\r\n",
    "            sms[bit] = sm\r\n",
    "            one[bit] = cnt\r\n",
    "\r\n",
    "        @functools.lru_cache(None)\r\n",
    "        def cal(p, mask):\r\n",
    "            if mask == 0:\r\n",
    "                # 已经没有工作了, 不再需要时间\r\n",
    "                return 0\r\n",
    "            if p == k:\r\n",
    "                # 此时mask不是0, 还有额外工作, 属于无效情况\r\n",
    "                return float('inf')\r\n",
    "            mn = float('inf')\r\n",
    "            cur = mask\r\n",
    "            while cur:\r\n",
    "                # 子集枚举\r\n",
    "                sm = sms[cur]\r\n",
    "                if sm < mn:\r\n",
    "                    # 只有当sm小于当前mn才有意义继续计算\r\n",
    "                    nex = mask ^ cur\r\n",
    "                    if k - p - 1 <= one[nex]:\r\n",
    "                        # 剪枝, 只有当后面的工作数>=人数时才继续计算\r\n",
    "                        mn = min(mn, max(sm, cal(p + 1, nex)))\r\n",
    "                cur = (cur - 1) & mask\r\n",
    "            return mn\r\n",
    "\r\n",
    "        return cal(0, uplimit - 1)\r\n",
    "\r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumTimeRequired(self, jobs: List[int], k: int) -> int:\n",
    "        n = len(jobs)\n",
    "        job_dict = {i: 0 for i in range(k)}\n",
    "        cur_idx = 0\n",
    "        for job in jobs:\n",
    "            job_dict[cur_idx % k] += job\n",
    "            cur_idx += 1\n",
    "        ans = [max(job_dict.values())]\n",
    "        job_dict = {i: 0 for i in range(k)}\n",
    "        visited_set = set()\n",
    "        cur_max = [0]\n",
    "        def dfs(cur):\n",
    "            if tuple(sorted(job_dict.values())) in visited_set:\n",
    "                return\n",
    "            if cur == n:\n",
    "                ans[0] = min(ans[0], cur_max[0])\n",
    "                return\n",
    "            for i in range(k):\n",
    "                if job_dict[i] + jobs[cur] >= ans[0]:\n",
    "                    continue\n",
    "                job_dict[i] += jobs[cur]\n",
    "                pre_max = cur_max[0]\n",
    "                cur_max[0] = max(cur_max[0], job_dict[i])\n",
    "                dfs(cur + 1)\n",
    "                cur_max[0] = pre_max\n",
    "                job_dict[i] -= jobs[cur]\n",
    "            visited_set.add(tuple(sorted(job_dict.values())))\n",
    "        dfs(0)\n",
    "        return ans[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from functools import lru_cache\n",
    "class Solution:\n",
    "    def minimumTimeRequired(self, jobs: List[int], k: int) -> int:\n",
    "        n = len(jobs)\n",
    "        tmp = {0: 0}\n",
    "        for i in range(n):\n",
    "            tmp[1<<i] = jobs[i]\n",
    "        cost = [0]*(1<<n)\n",
    "        for i in range(1<<n):\n",
    "            cost[i] = cost[i&(i-1)] + tmp[i-(i&(i-1))]\n",
    "        # print(cost,tmp)\n",
    "        @lru_cache(None)\n",
    "        def dfs(idx, state):\n",
    "            res = float('inf')\n",
    "            if idx == k:\n",
    "                return res if state else 0\n",
    "            if state == 0:\n",
    "                return 0\n",
    "            cur = state\n",
    "            total = cost[state]\n",
    "            while cur:\n",
    "                t = cost[cur]\n",
    "                # print(idx,cur,t)\n",
    "                if t < res:\n",
    "                    res = min(res, max(t,dfs(idx+1,state-cur)))\n",
    "                cur = (cur-1)&state\n",
    "            # print(idx,state,res,'memo')\n",
    "            return res \n",
    "        return dfs(0,(1<<n)-1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumTimeRequired(self, jobs: List[int], k: int) -> int:\n",
    "\n",
    "        @lru_cache(None)\n",
    "        def available_jobs(todo_bitmap, i):\n",
    "            while (1 << i) & todo_bitmap == 0 and i < len(jobs):\n",
    "                i += 1\n",
    "            if i == len(jobs):\n",
    "                return [(0, 0)]\n",
    "            else:\n",
    "                res = []\n",
    "                for my_jobs, my_cost in available_jobs(todo_bitmap, i + 1):\n",
    "                    res.append((my_jobs, my_cost))\n",
    "                    res.append(((my_jobs | (1 << i)), my_cost + jobs[i]))\n",
    "                return res\n",
    "\n",
    "        def next_available_job(todo_jobs):\n",
    "            for i in range(len(jobs)):\n",
    "                if (1 << i) & todo_jobs != 0:\n",
    "                    return i\n",
    "                \n",
    "        @lru_cache(None)\n",
    "        def dp(todo_bitmap, worker_id):\n",
    "            if worker_id == k:\n",
    "                if todo_bitmap == 0:\n",
    "                    return 0\n",
    "                else:\n",
    "                    return float(\"inf\")\n",
    "            if todo_bitmap == 0:\n",
    "                return 0\n",
    "            res = float(\"inf\")\n",
    "            i = next_available_job(todo_bitmap)\n",
    "            todo_bitmap -= 1 << i\n",
    "            \n",
    "            for my_jobs, my_cost in available_jobs(todo_bitmap, i + 1):\n",
    "                if my_cost + jobs[i] > res:\n",
    "                    continue\n",
    "                next_todo_bitmap = todo_bitmap - my_jobs\n",
    "                res = min(res, max(my_cost + jobs[i], dp(next_todo_bitmap, worker_id + 1)))\n",
    "            return res\n",
    "        res = dp((1 << len(jobs)) - 1, 0)\n",
    "        dp.cache_clear()\n",
    "        available_jobs.cache_clear()\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumTimeRequired(self, jobs: List[int], k: int) -> int:\n",
    "\n",
    "        @lru_cache(None)\n",
    "        def available_jobs(todo_bitmap, i):\n",
    "            while (1 << i) & todo_bitmap == 0 and i < len(jobs):\n",
    "                i += 1\n",
    "            if i == len(jobs):\n",
    "                return [(0, 0)]\n",
    "            else:\n",
    "                res = []\n",
    "                for my_jobs, my_cost in available_jobs(todo_bitmap, i + 1):\n",
    "                    res.append((my_jobs, my_cost))\n",
    "                    res.append(((my_jobs | (1 << i)), my_cost + jobs[i]))\n",
    "                return res\n",
    "\n",
    "        def next_available_job(todo_jobs):\n",
    "            for i in range(len(jobs)):\n",
    "                if (1 << i) & todo_jobs != 0:\n",
    "                    return i\n",
    "                \n",
    "        @lru_cache(None)\n",
    "        def dp(todo_bitmap, worker_id):\n",
    "            if worker_id == k:\n",
    "                if todo_bitmap == 0:\n",
    "                    return 0\n",
    "                else:\n",
    "                    return float(\"inf\")\n",
    "            if todo_bitmap == 0:\n",
    "                return 0\n",
    "            res = float(\"inf\")\n",
    "            i = next_available_job(todo_bitmap)\n",
    "            todo_bitmap -= 1 << i\n",
    "            \n",
    "            for my_jobs, my_cost in available_jobs(todo_bitmap, i + 1):\n",
    "                if my_cost + jobs[i] > res:\n",
    "                    continue\n",
    "                next_todo_bitmap = todo_bitmap - my_jobs\n",
    "                res = min(res, max(my_cost + jobs[i], dp(next_todo_bitmap, worker_id + 1)))\n",
    "            return res\n",
    "        res = dp((1 << len(jobs)) - 1, 0)\n",
    "        dp.cache_clear()\n",
    "        available_jobs.cache_clear()\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumTimeRequired(self, jobs: List[int], k: int) -> int:\n",
    "        if (length := len(jobs)) == k:\n",
    "            return max(jobs)\n",
    "        # 穷举是阶乘级别的复杂度\n",
    "\n",
    "        @functools.lru_cache(None)\n",
    "        def dfs(s: int, k: int):\n",
    "            pos0, cnt0, tot, maxleft = [], 0, 0, 0\n",
    "            for i in range(length):\n",
    "                if (s >> i) & 1 == 0:\n",
    "                    cnt0 += 1\n",
    "                    tot += jobs[i]\n",
    "                    maxleft = max(maxleft, jobs[i])\n",
    "                    pos0.append(i)\n",
    "            if k >= cnt0:\n",
    "                return maxleft\n",
    "            if k == 1:\n",
    "                return tot\n",
    "            \n",
    "            res = 120000000\n",
    "            # 从pos0中选span个赋为'1'\n",
    "            for span in range(1, cnt0-(k-1)+1):\n",
    "                choice = itertools.combinations(pos0, span)\n",
    "                for c in choice:\n",
    "                    tmp = s\n",
    "                    nowmax = 0\n",
    "                    for i in c:\n",
    "                        tmp = tmp | (1 << i)\n",
    "                        nowmax += jobs[i]\n",
    "                        if nowmax >= res:\n",
    "                            break\n",
    "                    cur = max(nowmax, dfs(tmp, k-1))\n",
    "                    res = min(res, cur)\n",
    "            return res\n",
    "        \n",
    "        return dfs(0, k)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumTimeRequired(self, jobs: List[int], k: int) -> int:\n",
    "        n = len(jobs)\n",
    "        if k == n: return max(jobs)\n",
    "        \n",
    "#         Log = [0] * (1 << n)\n",
    "#         for i in range(2, 1 << n):\n",
    "#             Log[i] = Log[i >> 1] + 1\n",
    "#         pre = [0] * (1 << n)\n",
    "#         for i in range(1, 1 << n):\n",
    "#             pre[i] = pre[i - (i & -i)] + jobs[Log[i & -i]]\n",
    "\n",
    "#         dp = [[float(\"inf\")] * k for _ in range(1 << n)]\n",
    "#         for i in range(k): dp[0][i] = 0\n",
    "#         for mask in range(1 << n):\n",
    "#             for j in range(k):\n",
    "#                 if not j:\n",
    "#                     dp[mask][j] = pre[mask]\n",
    "#                 else:\n",
    "#                     sub = (mask - 1) & mask\n",
    "#                     while sub:\n",
    "#                         dp[mask][j] = min(dp[mask][j], max(pre[sub], dp[mask ^ sub][j - 1]))\n",
    "#                         sub = (sub - 1) & mask\n",
    "#         return dp[-1][-1]\n",
    "\n",
    "        @lru_cache(None)\n",
    "        def dp(i, mask):\n",
    "            if i == k - 1:\n",
    "                ans = 0\n",
    "                for j in range(n):\n",
    "                    if not mask >> j & 1:\n",
    "                        ans += jobs[j]\n",
    "                return ans\n",
    "            cand = []\n",
    "            for j in range(n):\n",
    "                if not mask >> j & 1:\n",
    "                    cand.append(j)\n",
    "            ans = float(\"inf\")\n",
    "            m = len(cand)\n",
    "            for j in range(1, m - k + i + 2):\n",
    "                for sub in itertools.combinations(cand, j):\n",
    "                    cur = 0\n",
    "                    tmp = 0\n",
    "                    for s in sub:\n",
    "                        cur += jobs[s]\n",
    "                        tmp |= 1 << s\n",
    "                    tmp2 = dp(i + 1, mask | tmp)\n",
    "                    ans = min(ans, max(cur, tmp2))\n",
    "            return ans\n",
    "\n",
    "        return dp(0, 0)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "child = [[] for _ in range(1<<12)]\n",
    "for i0 in range(1,1<<12):\n",
    "    i = i0 \n",
    "    while i: \n",
    "        if i < i0 ^ i : \n",
    "            child[i0].append(i) \n",
    "        i = i-1 & i0 \n",
    "class Solution:\n",
    "    def minimumTimeRequired(self, jobs: List[int], k: int) -> int:\n",
    "        n = len(jobs) \n",
    "        s = [0] * (1<<n) \n",
    "        for i in range(n): s[1<<i] = jobs[i] \n",
    "        for i in range(1<<n): s[i] = s[-i&i] + s[i^-i&i] \n",
    "        @cache \n",
    "        def f(k,mask):\n",
    "            if k == 1: return s[mask]\n",
    "            if k & 1 : return min(max(f(k-1,x),s[x^mask]) for x in child[mask] if x.bit_count()>=k-1)\n",
    "            k >>= 1 \n",
    "            return min(\n",
    "                max(f(k,x),f(k,mask^x))\n",
    "                for x in child[mask] \n",
    "                if x.bit_count() >= k and (mask^x).bit_count() >= k \n",
    "            )\n",
    "        return f(k,(1<<n)-1)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import numpy as np\n",
    "class Solution:\n",
    "    def minimumTimeRequired(self, jobs: List[int], k: int) -> int:\n",
    "        Min, Max, n = max(jobs), sum(jobs), len(jobs)\n",
    "        def calc():\n",
    "            low, high = Min, Max\n",
    "            while low < high:\n",
    "                mid, cur, cnt, m = (low + high) // 2, 0, 1, 0\n",
    "                for a in jobs:\n",
    "                    if cur + a<=mid: cur+=a\n",
    "                    else: cur, cnt = a, cnt +1\n",
    "                    m = max(m, cur)\n",
    "                if cnt <= k: high = m\n",
    "                else: low = mid + 1\n",
    "            return low;\n",
    "        ans = inf\n",
    "        loop = min(int(100 * log(Min)), np.math.factorial(n))\n",
    "        for _ in range(loop):\n",
    "            np.random.seed(3104+_)\n",
    "            np.random.shuffle(jobs)\n",
    "            ans = min(ans, calc())\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumTimeRequired(self, jobs: List[int], k: int) -> int:\n",
    "\n",
    "        epoch = 10\n",
    "        decay = 0.97\n",
    "        import random \n",
    "        import numpy as np\n",
    "        self.ans = 1e9\n",
    "        if k == 1:\n",
    "            return sum(jobs)\n",
    "\n",
    "        def check():\n",
    "            worker_time = [0 for _ in range(k)]\n",
    "            for job in jobs:\n",
    "                a_idx = 0\n",
    "                for b_idx in range(1, k ):\n",
    "                    if worker_time[a_idx] > worker_time[b_idx]:\n",
    "                        a_idx = b_idx\n",
    "                worker_time[a_idx] += job\n",
    "            cur = max(worker_time)\n",
    "            # print(worker_time)\n",
    "            self.ans = min(cur, self.ans)\n",
    "            return cur \n",
    "\n",
    "        def simmulate_anneal():\n",
    "            random.shuffle(jobs)\n",
    "            t = 1e6\n",
    "            while t > 1e-5:\n",
    "                a = random.randint(0, len(jobs) - 1)\n",
    "                b = random.randint(0, len(jobs) - 1)\n",
    "                if a == b :\n",
    "                    continue \n",
    "                x = check()\n",
    "                jobs[a], jobs[b] = jobs[b],jobs[a]\n",
    "                y = check()\n",
    "\n",
    "                delta = y - x \n",
    "                if delta < 0 :\n",
    "                    continue\n",
    "                else:\n",
    "                    if exp(-delta / t) > random.random():\n",
    "                        jobs[a], jobs[b] = jobs[b],jobs[a]\n",
    "                t *= decay\n",
    "\n",
    "        for i in range(epoch):\n",
    "            simmulate_anneal()\n",
    "        return self.ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumTimeRequired(self, jobs: List[int], k: int) -> int:\n",
    "\n",
    "        epoch = 15\n",
    "        decay = 0.96\n",
    "        import random \n",
    "        import numpy as np\n",
    "        self.ans = 1e9\n",
    "        if k == 1:\n",
    "            return sum(jobs)\n",
    "\n",
    "        def check():\n",
    "            worker_time = [0 for _ in range(k)]\n",
    "            for job in jobs:\n",
    "                a_idx = 0\n",
    "                for b_idx in range(1, k ):\n",
    "                    if worker_time[a_idx] > worker_time[b_idx]:\n",
    "                        a_idx = b_idx\n",
    "                worker_time[a_idx] += job\n",
    "            cur = max(worker_time)\n",
    "            # print(worker_time)\n",
    "            self.ans = min(cur, self.ans)\n",
    "            return cur \n",
    "\n",
    "        def simmulate_anneal():\n",
    "            random.shuffle(jobs)\n",
    "            t = 1e6\n",
    "            while t > 1e-5:\n",
    "                a = random.randint(0, len(jobs) - 1)\n",
    "                b = random.randint(0, len(jobs) - 1)\n",
    "                if a == b :\n",
    "                    continue \n",
    "                x = check()\n",
    "                jobs[a], jobs[b] = jobs[b],jobs[a]\n",
    "                y = check()\n",
    "\n",
    "                delta = y - x \n",
    "                if delta < 0 :\n",
    "                    continue\n",
    "                else:\n",
    "                    if exp(-delta / t) > random.random():\n",
    "                        jobs[a], jobs[b] = jobs[b],jobs[a]\n",
    "                t *= decay\n",
    "\n",
    "        for i in range(epoch):\n",
    "            simmulate_anneal()\n",
    "        return self.ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumTimeRequired(self, jobs: List[int], k: int) -> int:\n",
    "\n",
    "        epoch = 15\n",
    "        decay = 0.96\n",
    "        import random \n",
    "        import numpy as np\n",
    "        self.ans = 1e9\n",
    "        if k == 1:\n",
    "            return sum(jobs)\n",
    "\n",
    "        def check():\n",
    "            worker_time = [0 for _ in range(k)]\n",
    "            for job in jobs:\n",
    "                a_idx = 0\n",
    "                for b_idx in range(1, k ):\n",
    "                    if worker_time[a_idx] > worker_time[b_idx]:\n",
    "                        a_idx = b_idx\n",
    "                worker_time[a_idx] += job\n",
    "            cur = max(worker_time)\n",
    "            # print(worker_time)\n",
    "            self.ans = min(cur, self.ans)\n",
    "            return cur \n",
    "\n",
    "        def simmulate_anneal():\n",
    "            random.shuffle(jobs)\n",
    "            t = 1e6\n",
    "            while t > 1e-5:\n",
    "                a = random.randint(0, len(jobs) - 1)\n",
    "                b = random.randint(0, len(jobs) - 1)\n",
    "                if a == b :\n",
    "                    continue \n",
    "                x = check()\n",
    "                jobs[a], jobs[b] = jobs[b],jobs[a]\n",
    "                y = check()\n",
    "\n",
    "                delta = y - x \n",
    "                if delta < 0 :\n",
    "                    continue\n",
    "                else:\n",
    "                    if exp(-delta / t) > random.random():\n",
    "                        jobs[a], jobs[b] = jobs[b],jobs[a]\n",
    "                t *= decay\n",
    "\n",
    "        for i in range(epoch):\n",
    "            simmulate_anneal()\n",
    "        return self.ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import numpy as np\n",
    "class Solution:\n",
    "    def minimumTimeRequired(self, jobs: List[int], k: int) -> int:\n",
    "        Min,Max,n=max(jobs),sum(jobs),len(jobs)\n",
    "        def calc():\n",
    "            low,high=Min,Max\n",
    "            while low<high:\n",
    "                mid,cur,cnt,m=(low+high)//2,0,1,0\n",
    "                for a in jobs:\n",
    "                    if cur+a<=mid:\n",
    "                        cur+=a\n",
    "                    else:\n",
    "                        cur,cnt=a,cnt+1\n",
    "                    m=max(m,cur)\n",
    "                if cnt<=k:high=m\n",
    "                else:low=mid+1\n",
    "            return low;\n",
    "        ans=inf\n",
    "        print(min(int(200*log(Min)),np.math.factorial(n)))\n",
    "        for _ in range(min(int(200*log(Min)),np.math.factorial(n))):\n",
    "            np.random.seed(66+_)\n",
    "            np.random.shuffle(jobs)\n",
    "            ans=min(ans,calc())\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from functools import lru_cache\n",
    "class Solution:\n",
    "    def minimumTimeRequired(self, jobs: List[int], k: int) -> int:\n",
    "        @lru_cache(maxsize = None)\n",
    "        def f(cur, jobs):\n",
    "            if not jobs:\n",
    "                return max(cur)\n",
    "            j0, jr = jobs[0], jobs[1:]\n",
    "\n",
    "            m = 1e8\n",
    "            for i in range(len(cur)):\n",
    "                nc = tuple(sorted((*cur[:i], cur[i]+j0, *cur[i+1:])))\n",
    "                if max(nc) > m:\n",
    "                    continue\n",
    "                r = f(nc, jr)\n",
    "                m = min(m, r)\n",
    "            return m\n",
    "\n",
    "        res, jobs = (0,) * k, tuple(jobs)\n",
    "        return f(res, jobs)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "subsets = [[] for _ in range(1 << 12)]\n",
    "for s in range(1 << 12):\n",
    "    sub = s & (s - 1)\n",
    "    while sub:\n",
    "        subsets[s].append(sub)\n",
    "        sub = (sub - 1) & s\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def minimumTimeRequired(self, jobs: List[int], k: int) -> int:\n",
    "        n = len(jobs)\n",
    "        all_state = 1 << n\n",
    "        base = [0] * all_state\n",
    "        bit = 1\n",
    "        for i in range(n):\n",
    "            for j in range(bit):\n",
    "                base[bit | j] = base[j] + jobs[i]\n",
    "            bit <<= 1\n",
    "\n",
    "        dp = base.copy()\n",
    "        for i in range(1, k):\n",
    "            for s in range(all_state - 1, 0, -1):\n",
    "                for sub in subsets[s]:\n",
    "                    comp = s ^ sub\n",
    "                    temp = dp[sub] if dp[sub] >= base[comp] else base[comp]\n",
    "                    if temp < dp[s]:\n",
    "                        dp[s] = temp\n",
    "        return dp[-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "subsets = [[] for _ in range(1 << 12)]\n",
    "for i in range(1 << 12):\n",
    "    s = i\n",
    "    while s:\n",
    "        subsets[i].append(s)\n",
    "        s = (s - 1) & i\n",
    "\n",
    "class Solution:\n",
    "    def minimumTimeRequired(self, cookies: List[int], k: int) -> int:\n",
    "        m = 1 << len(cookies)\n",
    "        SUM = [0] * m\n",
    "        for i, v in enumerate(cookies):\n",
    "            bit = 1 << i\n",
    "            for j in range(bit):\n",
    "                SUM[bit | j] = SUM[j] + v\n",
    "\n",
    "        f = SUM.copy()\n",
    "        for _ in range(1, k):\n",
    "            for j in range(m - 1, 0, -1):\n",
    "                for s in subsets[j]:\n",
    "                    v = f[j ^ s]\n",
    "                    if SUM[s] > v: v = SUM[s]  # 不要用 max 和 min，那样会有额外的函数调用开销\n",
    "                    if v < f[j]: f[j] = v\n",
    "        return f[-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "sub_set = [[] for _ in range(1 << 12)]\n",
    "for i in range(1 << 12):\n",
    "    x = i\n",
    "    while x > 0:\n",
    "        sub_set[i].append(x)\n",
    "        x = (x - 1) & i\n",
    "\n",
    "class Solution:\n",
    "    def minimumTimeRequired(self, jobs: List[int], k: int) -> int:\n",
    "        n = len(jobs)\n",
    "        job_sum = [0] * (1 << n)\n",
    "        for i, v in enumerate(jobs):\n",
    "            tmp = 1 << i\n",
    "            for j in range(tmp):\n",
    "                job_sum[tmp | j] = job_sum[j] + v\n",
    "\n",
    "        for i in range(1, 1 << n):\n",
    "            job_sum[i] = sum([jobs[j] for j in range(n) if (i >> j) & 1])\n",
    "        dp = list(job_sum)\n",
    "\n",
    "        for _ in range(1, k):\n",
    "            for j in range((1 << n) - 1, 0, -1):\n",
    "                for m in sub_set[j]:\n",
    "                    tmp = job_sum[m]\n",
    "                    if tmp < dp[j-m]:\n",
    "                        tmp = dp[j-m]\n",
    "                    if tmp < dp[j]:\n",
    "                        dp[j] = tmp\n",
    "        return dp[-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "subsets = [[] for _ in range(1 << 12)]\n",
    "for i in range(1 << 12):\n",
    "    s = i\n",
    "    while s:\n",
    "        subsets[i].append(s)\n",
    "        s = (s - 1) & i\n",
    "\n",
    "class Solution:\n",
    "    def minimumTimeRequired(self, jobs: List[int], k: int) -> int:\n",
    "        n = len(jobs)\n",
    "        total = [0]*(1<<n)\n",
    "        for i,v in enumerate(jobs):\n",
    "            bit = 1<<i \n",
    "            for j in range(bit):\n",
    "                total[bit|j] = total[j]+v\n",
    "\n",
    "        dp = [[inf]*(1<<n) for _ in range(k)] \n",
    "        dp[0] = total[::]\n",
    "        for i in range(1,k):\n",
    "            for mask in range(1<<n):\n",
    "                for sub in subsets[mask]:\n",
    "                    v =dp[i-1][mask^sub] \n",
    "                    if total[sub]>v:\n",
    "                        v = total[sub]\n",
    "                    if v<dp[i][mask]:\n",
    "                        dp[i][mask] = v\n",
    "        return dp[k-1][-1] \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumTimeRequired(self, jobs: List[int], k: int) -> int:\n",
    "        if (length := len(jobs)) == k:\n",
    "            return max(jobs)\n",
    "        # 穷举是阶乘级别的复杂度\n",
    "\n",
    "        s = '0' * length\n",
    "        @functools.lru_cache(None)\n",
    "        def dfs(s: str, k: int):\n",
    "            ## 用十二位二进制表示更好\n",
    "            pos0, cnt0, tot, maxleft = [], 0, 0, 0\n",
    "            for i in range(length):\n",
    "                if s[i] == '0':\n",
    "                    pos0.append(i)\n",
    "                    cnt0 += 1\n",
    "                    maxleft = max(maxleft, jobs[i])\n",
    "                    tot += jobs[i]\n",
    "            if k >= cnt0:\n",
    "                return maxleft\n",
    "            if k == 1:\n",
    "                return tot\n",
    "            \n",
    "            res = float('inf')\n",
    "            # 从pos0中选span个赋为'1'\n",
    "            for span in range(1, cnt0-(k-1)+1):\n",
    "                choice = itertools.combinations(pos0, span)\n",
    "                for c in choice:\n",
    "                    tmp = list(s)\n",
    "                    nowmax = 0\n",
    "                    for i in c:\n",
    "                        tmp[i] = '1'\n",
    "                        nowmax += jobs[i]\n",
    "                        if nowmax >= res:\n",
    "                            break\n",
    "                    cur = max(nowmax, dfs(''.join(tmp), k-1))\n",
    "                    res = min(res, cur)\n",
    "            return res\n",
    "        \n",
    "        return dfs(s, k)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "subsets = [[] for _ in range(1 << 12)]\n",
    "for i in range(1 << 12):\n",
    "    s = i\n",
    "    while s:\n",
    "        subsets[i].append(s)\n",
    "        s = (s - 1) & i\n",
    "\n",
    "class Solution:\n",
    "    def minimumTimeRequired(self, jobs: List[int], k: int) -> int:\n",
    "        \n",
    "        n = 1 << len(jobs) \n",
    "        sum_ = [0] * n\n",
    "        for i, v in enumerate(jobs):\n",
    "            bit = 1 << i\n",
    "            for j in range(bit):\n",
    "                sum_[bit | j] = sum_[j] + v\n",
    "        \n",
    "        f = sum_.copy()\n",
    "        for _ in range(1, k):\n",
    "            for j in range(n - 1, 0, -1):\n",
    "                for s in subsets[j]:\n",
    "                    v = f[j ^ s]\n",
    "                    if sum_[s] > v : v = sum_[s]\n",
    "                    if v < f[j]: f[j] = v\n",
    "                    \n",
    "        \n",
    "        return f[-1]\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "subsets = [[] for _ in range(1 << 12)]\n",
    "for i in range(1 << 12):\n",
    "    s = i\n",
    "    while s:\n",
    "        subsets[i].append(s)\n",
    "        s = (s - 1) & i\n",
    "\n",
    "class Solution:\n",
    "    def minimumTimeRequired(self, cookies: List[int], k: int) -> int:\n",
    "        m = 1 << len(cookies)\n",
    "        SUM = [0] * m\n",
    "        for i, v in enumerate(cookies):\n",
    "            bit = 1 << i\n",
    "            for j in range(bit):\n",
    "                SUM[bit | j] = SUM[j] + v\n",
    "\n",
    "        f = SUM.copy()\n",
    "        for _ in range(1, k):\n",
    "            for j in range(m - 1, 0, -1):\n",
    "                for s in subsets[j]:\n",
    "                    v = f[j ^ s]\n",
    "                    if SUM[s] > v: v = SUM[s]  # 不要用 max 和 min，那样会有额外的函数调用开销\n",
    "                    if v < f[j]: f[j] = v\n",
    "        return f[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "#预处理出所有状态的子集\n",
    "subset=[[] for _ in range(1<<12)]\n",
    "for j in range(1<<12):\n",
    "    s=j\n",
    "    while s:\n",
    "        subset[j].append(s)\n",
    "        s=(s-1)&j\n",
    "class Solution:\n",
    "    def minimumTimeRequired(self, jobs: List[int], k: int) -> int:\n",
    "        #状态压缩,动态规划\n",
    "        n=len(jobs)\n",
    "        m=1<<n\n",
    "        #dp[i][j]表示完成前k个工人,完成状态为j时的最小的单个最大工作时间。\n",
    "        #预处理状态为j的工作时间\n",
    "        check=[0]*m\n",
    "        for j in range(m):\n",
    "            for p in range(n):\n",
    "                if j>>p&1: check[j]+=jobs[p]\n",
    "        dp=[[0]*m for _ in range(k)]\n",
    "        dp[0]=check\n",
    "        for i in range(1,k):\n",
    "            for j in range(1,m):\n",
    "                dp[i][j]=inf\n",
    "                for s in subset[j]:\n",
    "                    v=dp[i-1][j^s]\n",
    "                    if check[s]>v: v=check[s]\n",
    "                    if v<dp[i][j]: dp[i][j]=v\n",
    "        return dp[k-1][m-1]"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
